# 第一个错误的版本: https://leetcode-cn.com/problems/first-bad-version/

def isBadVersion():
    pass

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        这道问题就是要求时间复杂度尽量的低，那么顺序查找时间复杂度O(n)满足不了需求。就开始考虑 二分查找，时间复杂度更低
        以测试测试得例子为例： 1 2 3 4 5  bad = 4， 注意错误的版本，他之后的所有版本都会错误。锁所以后面的 5 也等价于 4，那么就等于：
        1 2 3 4 4 
        我们需要从这里找到 target = 4, 且第一次出现！ 问题就很明显了，被抽象为 二分查找求第一次出现的 target！
        """

        left , right = 1, n
        # 采用第二种方法：不断在循环体排除不存在的区间
        while left < right:
            mid = left + (right - left) // 2  # 不需要加1，往左边偏
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        
        return left


class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """

        left , right = 1, n
        # 采用第一种方法：不断在循环体里面找到第一个错误的版本
        while left <= right:
            mid = left + (right - left) // 2  # 不需要加1，往左边偏
            if isBadVersion(mid):
                if mid == 1 or not isBadVersion(mid-1):
                    return mid
                right = mid - 1
            else:
                left = mid + 1